home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Magnum One
/
Magnum One (Mid-American Digital) (Disc Manufacturing).iso
/
d14
/
atre12.arc
/
ATREE.DOC
< prev
next >
Wrap
Text File
|
1991-07-27
|
58KB
|
1,613 lines
An Implementation of Adaptive Logic Networks
~~ ~~~~~~~~~~~~~~ ~~ ~~~~~~~~ ~~~~~ ~~~~~~~~
copyright W.W. Armstrong and Andrew Dwelly
November 11, 1990
bug-fixes and initial port to DOS
Rolf Manderschied
April 15, 1991
revised for Microsoft Windows
Monroe M. Thomas
May 31, 1991
1 Introduction
~ ~~~~~~~~~~~~
The Windows dynamic link library atree.dll contains an implementation of
an unconventional kind of learning algorithm for adaptive logic
networks[Arms], which can be used in place of the backpropagation
algorithm for multilayer feedforward artificial neural networks [Hech],
[Rume].
The ability of a logic network to learn or adapt to produce an arbitrary
boolean function specified by some empirical "training" data is certainly
important for the success of the method, but there is another property of
logic networks which is also essential. It is the ability to generalize
their responses to new inputs, presented after training is completed. The
successful generalization properties of these logic networks are based on
the observation, backed up by a theory [Boch], that trees of two-input
logic gates of types AND, OR, LEFT, and RIGHT are very insensitive to
changes of their inputs.
Some experiments on handwritten numeral recognition and satellite image
classification have been successfully carried out. [Arms3, Arms4]. Recent
experiments have shown this algorithm to learn quickly on some problems
requiring learning of integer or continuous-valued functions where
backpropagation has reportedly led to long training times; and it
functions very well on boolean data [Arms5].
At the present time, only limited comparisons have been made with the
conventional approach to neurocomputing, so the claims necessarily have to
be muted. This situation should rapidly be overcome as users of this
software (or improved variants of it yet to come) begin experimentation.
However one property of these networks in comparison to others is an
absolute, and will become apparent to computer scientists just by
examining the basic architecture of the networks. Namely, when special
hardware is available, this technique, because it is based on
combinational logic circuits of limited depth (e. g. 10 to 20 propagation
delays), can potentially offer far greater execution speeds than other
techniques which depend on floating point multiplications, additions, and
computation of sigmoidal functions.
A description of the class of learning algorithms and their hardware
realizations can be found in [Arms, Arms2], but we will briefly introduce
the concepts here. An atree (Adaptive TREE) is a binary tree with nodes of
two types: (1) adaptive elements, and (2) leaves. Each element can
operate as an AND, OR, LEFT, or RIGHT gate, depending on its state. The
state is determined by two counters which change only during training.
The leaf nodes of the tree serve only to collect the inputs to the subtree
of elements. Each one takes its input bit from a boolean input vector or
from the vector consisting of the complemented bits of the boolean input
vector. The tree produces a single bit as its output.
-1-
Despite the apparent limitation to boolean data, simple table-lookups permit
representing non-boolean input values (integers or reals for example) as bit
vectors, and these representations are concatenated and complemented to form
the inputs at the leaves of the tree. For computing non-boolean outputs,
several trees are used in parallel to produce a vector of bits representing
the output value.
This software contains everything needed for a programmer with knowledge of
C and Windows 3.x to create, train, evaluate, and print out adaptive logic
networks. It has been written for clarity rather than speed in the hope that
it will aid the user in understanding the algorithms involved. The
intention was to try make this version faster than variants of the
backpropagation algorithm for learning, and to offer much faster evaluation
of learned functions than the standard approach given the same
general-purpose computing hardware. Users of the software are requested to
provide some feedback on this point to the authors.
This software also includes a language "lf" that allows a non-programmer
to conduct experiments using atrees, as well as a number of
demonstrations.
A version of this software which is both faster and contains a more
effective learning algorithm is planned for the near future.
Y
│
┌───────┴───────┐
│ Random Walk │
│ Decoder │
└───────┬───────┘
┌───────┴───────┐
│ Output Vector │
└┬─────────────┬┘
│ │
Trees - one per (O) (O)
output bit │ │
┌─────┴────┐ ┌─┴─┐
(O)─┘ └─(O)
│ │
┌─┴─┐ ┌─┴─┐
(O)┘ └(O) (O)┘ └(O)
┌─┴─┐ ┌─┴─┐ ┌─┴─┐ ┌─┴─┐
│ │ │ │ │ │ │ │
b1 ~b1 b2 ~b1 ~b1 ~b2 b2 ~b2 Random Connections
┌──────┬──────┐
│ ~b1 │ ~b2 │ Complements
└──┬───┴──┬───┘
┌──────────────────┘ │
│ ┌──────────────────┘
┌──┴───┬──┴───┐
│ b1 │ b2 │ Input Vector
└──┬───┴──┬───┘
┌────┴──────┴───┐
│ Random Walk │
│ Encoder │
└───┬───────┬───┘
│ │
X1 X2
Figure 1: Using several trees to compute Y = ƒ(X1, X2)
-2-
2 Writing Applications With atree
~ ~~~~~~~ ~~~~~~~~~~~~ ~~~~ ~~~~~
Writing applications that perform a simple classification (yes or no) is
relatively easy (within the constraints of Windows programming). The
programmer creates a training set, then creates a tree using atree_create.
The tree is trained using atree_train and then it can be used to evaluate
new inputs using atree_eval. Examples of this can be seen in the files
mosquito.c, and mult.c, both of which hide most of Windows' dressings
for clarity.
Writing applications where the tree has to learn real number valued
functions is a little more complex, as the programmer has to come to grips
with the encoding problem.
Because a single tree produces only one bit, the programmer must train
several trees on the input data, each one responsible for one bit of the
output data. This is made slightly simpler by the choice of parameters
for atree_train() which takes an array of bit vectors as the training set,
and an array of bit vectors for the result set. The programmer provides
an integer which states which bit column of the result set the current tree
is being trained on. Typical code might look as follows:-
....
{
int i;
int j;
LPBIT_VEC train; /* LPBIT_VEC is a long (far) pointer to a bit_vec */
LPBIT_VEC result;
LPATREE *forest; /* LPATREE is a long (far) pointer to an atree */
/* Create the training set */
train = domain();
/* Create the result set */
result = codomain();
/*
* Make enough room for the set of trees - one tree per bit in the
* codomain
*/
forest = (LPATREE *) malloc((unsigned)sizeof(LPATREE) * NO_OF_TREES);
/* Now create and train each tree in turn */
for (i = 0; i < NO_OF_TREES; i++)
{
forest[i] = atree_create(variables,width);
atree_train(forest[i],train,result,i,TRAIN_SET_SIZE,
MIN_CORRECT,MAX_EPOCHS,VERBOSITY);
}
/*
* Where TRAIN_SET_SIZE is the number of elements in train,
* MIN_CORRECT is the minimum number of elements the tree should
* get correct before stopping, MAX_EPOCHS is the absolute maximum
* length of training and VERBOSITY controls the amount of
* diagnostic information produced.
*/
......
-3-
The standard encoding of integers into binary numbers does not work well
with this algorithm since it tends to produce functions which are
sensitive to the values of the least significant bit. So instead we use
the routine atree_rand_walk() to produce an array of bit vectors where each
vector is picked at random and is a specified Hamming distance away form
the previous element. Picking the width of the encoding vector, and the
size of the step in Hamming space is currently a matter of
experimentation, although some theory is currently under development to
guide this choice.
Real numbers are encoded by dividing the real number line into a number of
quantization levels, and placing each real number to be encoded into a
particular quantization. Obviously, the more quantizations there are, the
more accurate the encoding will be. Essentially this procedure turns real
numbers into integers for the purposes of training. The quantizations are
then turned into bit vectors using the random walk technique again.
Once the trees are trained, we can evaluate them with new inputs. Despite
their training, the trees may not be totally accurate, and we need some
way of dealing with error. The normal approach taken is to produce a
result from the set of trees, then search through the random walk for the
closest bit vector. This is taken as the true result. Typical code might
be as follows:-
....
/* Continued from previous example */
int closest_elem;
int smallest_diff;
int s;
LPBIT_VEC test;
LPBIT_VEC tree_result;
/* Now create the (single in this example) test vector */
test = test_element();
/* Now create some room for the tree results */
tree_result = bv_create(No_OF_TREES);
/* Evaluate the trees */
for (i = 0; i < NO_OF_TREES; i++)
{
/*
* Set bit i of tree_result, the result of evaluating
* the ith tree.
*/
bv_set(i, tree_result, atree_eval(forest[i], test));
}
-4-
/*
* tree_result probably has a few bits wrong, so we will look
* for the closest element in the result array
*/
closest_elem = 0;
smallest_diff = MAX_INT;
for (i = 0; i < TRAIN_SET_SIZE; i++)
{
if ((s = bv_diff(tree_result, result[i])) < smallest_diff)
{
smallest_diff = s;
closest_elem = i;
}
}
/*
* At this point, result[closest_elem] is the correct bit vector,
* and smallest_diff is the amount of error produced by the tree.
*/
do_something_with(result[closest_elem]);
/* Etc. */
}
....
-5-
3 The Windows atree Library
~ ~~~~~~~~~~~ ~~~~~ ~~~~~~~
The atree library consists of a single include file atree.h, which must be
included in all software making calls on the library, and a library of
routines atree.dll. The routines permit the creation, training, evaluation
and testing of adaptive logic networks in a Windows environment, and there
are a number of utility routines designed to make this task easier. Note
that the entire atree library has been compiled into a dynamic link library
(DLL) for use under Windows. It is only necessary to include all atree
library functions used in the IMPORTS section of the application's module
definition file. The source code for atree.dll can be found in atree.c,
which can be used to compile atree routines directly into an application if
desired.
The atree.dll is capable of supporting multiple instances of atree
applications, although (as expected), this can slow down tree training.
Mosquito.exe provides a good example of this: try clicking on the Run menu
option two or three times. Or try running mosquito.exe and mult.exe at the
same time.
3.1 Naming Conventions
Throughout this software, the following conventions have been used :-
Publicly available functions are called atree_something(). If the routine is
primarily concerned with bit vectors rather than atrees, it will be named
bv_something() instead. The exceptions to this occur for functions that are
directly responsible for maintaining performance of the atree software in
the Windows environment.
Variables are always in lower case. The variables i, j, and k are reserved
as iterators in "for" loops. The variable verbosity is reserved for
controlling the amount of diagnostic information produced.
3.2 The Main Data Structures
The two main data structures are atree and bit_vec which represent atrees
and bit vectors respectively. They are both fully specified in the file
atree.h.
Examining the structure atree first, we find a recursive structure which
represents a single node in an atree. Since it is binary, it consists of
the data which the node holds, and two pointers to child nodes. If the
subnode is a leaf of the tree it will contain a bit number rather than a
pointer, so both left and right are unions of pointers and integers to
represent these two possibilities.
The internal data of the node consists of a series of boolean flags
(represented by chars here), a char which describes the function of the node
(AND, OR, LEFT, or RIGHT), two chars for signals from the child nodes, and
two counters cnt_10 and cnt_01 used during training.
-6-
Leaf_flag actually represents two flags, and each nibble of the byte is set
to true if the left (or respectively, right) input of the node is a leaf
node, which represents a "lead" to be connected to a bit of the input vector
or its complement, rather than to an adaptive element. The left and right
nibbles of the flag cmp_flag are only meaningful if the corresponding nibble
in leaf_flag is true. They represent the fact that the value of the bit the
leaf accesses is complemented before it is input into the tree. The flag
seg_flag is used to mark nodes that are at the beginning of segments (offset
0), since these nodes will begin a new dynamically allocated global heap
segment.
Two important type definitions exist to facilitate access to the main data
structures. LPBIT_VEC is typedef'd as "bit_vec far *" (a long pointer to a
bit_vec). All bit_vec data structures should be declared with LPBIT_VEC.
Similarly, LPATREE is typedef'd as "atree far *" (a long pointer to an
atree). All atree data structures should be declared with LPATREE.
3.3 Manifest Constants
All the constants defined are internal to atree.c and are declared at the top
of this file.
Constants AND, OR, LEFT, RIGHT represent the current function of a node.
LEFTLEAF and RIGHTLEAF are used as masks for leaf_flag TRUE and FALSE are
used to represent boolean values both in program flags and also in the tree
itself. We also include UNEVALUATED and ATREE_ERROR in the boolean type.
These complete the type lattice for booleans, but more importantly allow us
to signal that a subtree has not been evaluated during training, or is in
error.
The constant MAX_RETRY is used in the random walk routines to control the
maximum amount of searching for a bit vector than has not previously been
encountered.
The constants MAXSET, ABOVEMID, BELOWMID, and MINSET are used during the
initialisation of a tree. The operation of a node in the tree is determined
by the value of its counters, the char atree.function in a node is
determined by them. The above constants represent the full range of a
counter and also mark its middle values.
The constants SEGLENGTH and NUMSEGS are used by the atree memory mangement
routines. SEGLENGTH defines the number of bytes in a data segment; NUMSEGS
defines the maximum number of dynamically allocated data segments allowed.
Note that bit vectors are allocated using the atree memory management
routines but that atrees themselves are allocated using Windows' global
memory routines, so the NUMSEGS restriction does not apply to trees.
3.4 Private Macros
The following macros are private to atree.c.
The macro Printf serves as a nice front end for the Windows API version of
sprintf, wsprintf.
The terms public and private are used to denote whether a routine is for
use outside the package (public) or is strictly internal (private). They
take advantage of the fact that in C, a routine that is declared as static
may not be accessed outside its source file.
The macro EVER is a standard C trick used to describe an infinite loop
typically it will be used with a for as in for EVER.
In order to print out a boolean value (in our raised definition of
booleans) we define the macro PRINTBOOL.
The macro VERBOSE is used to control the amount of diagnostic information
produced by a program. The variable verbosity is set to a particular level,
and if the statement s is associated with that or a lower level, it is
executed. Typically we will see the following sort of usage
VERBOSITY(1,diagnostic()); diagnostic() will be executed, providing the
verbosity level is greater or equal to 1.
The macro BYTE gives the size (in bits) of a byte on this machine. (OK,
this is a hold over from the UNIX version!)
The macros EVAL, LEFTEVAL,and RIGHTEVAL are used during tree evaluation.
They will be explained in detail in the routines that call them.
3.5 Public Macros
The following macros are defined in atree.h and are available to any
application using the atree library.
The macro MEMCHECK allows us to check the validity of a pointer. For
example, if the pointer p in MEMCHECK(p) is NULL, then a message box pops up
with appropriate notification, and the application is terminated.
The macro RANDOM allows us to conveniently produce a random number between 0
and some user-specified x in the program. For example, in order to produce a
random true or false value (0 or 1) we write RANDOM(2).
The macro Malloc serves as a front end for the atree memory allocation
routine WinMem_Malloc(). To allocate a chunk of 16 bytes to a pointer p,
use p = Malloc(16).
The macro Free serves as a front end for the atree memory routine
WinMem_Free(). To free the memory pointed by a pointer p that was allocated
with WinMem_Malloc() (or the macro Malloc), use Free(p).
3.6 Global Variables in atree.c
The global variables seg and freemem are used by the atree memory
management routines to maintain dynamically allocated data segments, and are
private to atree.c
-8-
3.7 The Windows atree API
The following routines are available to your application when developing
atree applications. Note that they are all available through atree.dll, so
the atree library functions do not need to be linked into an application.
Instead, simply include the needed atree library functions in the
application module definition file (see mosquito.def for an example).
Should the programmer choose, atree.c can be compiled and linked directly
into your application. If this is done, make sure the LibMain() function in
atree.c (see section 3.8.1) is commented out, as it serves as the DLL entry
point for the library.
3.7.1 void atree_init()
This routine should be called by the user before making calls to any other
atree library routine. Currently, it merely calls the srand() routine to
initialize the random number generator, but it may do more in future
versions.
3.7.2 LPBIT_VEC atree_rand_walk(num,width,p)
int num;
int width;
int p;
The standard encoding of integers into binary is not suitable for adaptive
logic networks, since the least significant bits vary quickly during
incrementations of the integer compared to the more significant bits. The
effect of binary number encoding is easy to see when we consider the result
of a single bit error occurring in the output of a collection of trees (a
forest): how important the error is depends on the position of the bit in
the output vector. An error in the least significant bit of the vector makes
a difference of one unit in the output integer; an error in the most
significant bit causes a large difference in the output integer depending on
the width of the vector.
A better encoding is one where each bit varies at about the same rate; and
we can create such an encoding by taking a random walk through Hamming space
[Smit]. A randomly produced vector is chosen to represent the first integer
value in a sequence. For each subsequent integer, a specified number of
bits, picked a random, are changed to create the next vector.
The routine atree_rand_walk() does this job, with the additional guarantee
that each vector produced is unique. The parameter num gives the number of
vectors, or "steps" in the walk, required, the parameter width gives the
width in bits of each vector, and the parameter p is the distance of each
step in the Hamming metric (the number of bits which change).
The uniqueness requirement makes the routine rather more complex than one
might expect. Because we expect to be using large random walks, it was felt
that a simple check against all the previously created vectors would not be
efficient enough. Instead all vectors with the same weight (the weight of a
bit vector is the number of 1s in it; e. g., the weight of 10110 is 3) are
chained together, and only those vectors with a weight equal to the one
currently being checked for uniqueness are examined. If the vector is not
-9-
unique, the routine will go back to the previous unique vector and try
randomly changing some other bits. In order to avoid an infinite loop, it
will only try MAX_RETRY times to do this. If it cannot proceed, the routine
aborts. A better version of the software would check to assure a minimum
distance between points.
3.7.3 public LPATREE atree_create(numvars,leaves)
int numvars;
int leaves;
This is the routine used to create an atree of a given size. The parameter
leaves gives the number of leaves or output leads to the tree, and hence
controls its size, which is one less than this. A balanced tree is chosen
if possible.
The parameter numvars is the number of boolean variables in the bit vector
input to the tree. It is used during initialization of the (random)
connections between leaf nodes of the tree and the input bit vector. Usually
the bits of the input vector, and their complements will be required as
inputs to the tree since there are no NOT nodes in the tree itself. It is
therefore recommended that there be at least twice as many inputs to the
tree as there are bits in the input vector for a given problem:
leaves >= 2 * numvars
The routine itself proceeds by deciding which bit of the input vector
is to be connected to each leaf, and stores the information in two
arrays connection which holds the bit numbers, and
complemented which shows whether the connection is complemented or
not. It then calls a private recursive tree-building routine
build_tree(). The latter routine depends on having enough space
already allocated on the heap and atree_create() is responsible
for that.
3.7.4 public BOOL atree_eval(tree,vec)
LPATREE tree;
LPBIT_VEC vec;
This routine is responsible for calculating the output of a tree from a
given bit vector. It takes advantage of the standard C definition of && and
|| to do this in the required parsimonious(1) fashion [Meis][Arms5]. The
Macro LEFTEVAL is responsible for evaluating the left subtree and RIGHTEVAL
is responsible for the right subtree. They both use the EVAL macro which is
a little complex since it has to check whether or not a node is a leaf and
is connected to the input bit-vector, and if it is, whether the value is to
be inverted or not.
This routine also marks subtrees that are unevaluated, and sets the internal
atree.sig_left and atree.sig_right values for a node. This information is
used when atree_eval() is used from within atree_train.
_______
(1) I really don't like this word - it makes me think of Scrooge (A.D.).
However, if you really had to pay for massive parallelism rather than
parsimonious parallelism, I suppose you could be persuaded to like the term
(W.A.). No I couldn't (A.D.).
3.7.5 public BOOL atree_train(tree,tset,...)
LPATREE tree
LPBIT_VEC tset;
LPBIT_VEC correct_result;
int bit_col;
int tset_size;
int no_correct;
int epochs;
int verbosity;
atree_train() is the routine that adapts a tree to learn a particular
function. It is a little more complex than you might expect as it has been
arranged to make it convenient to train multiple trees on the same training
set.
The parameter tree is the tree to be trained, and the parameter tset is the
array of bit vectors which the tree is to be trained on (the training set).
An atree only produces a single bit, so in principle all that is needed for
the correct_result parameter is an array of bits, with one bit corresponding
to each bit vector in the training set. In training multiple trees (when
learning a quantized real-valued function, for example), it is more
convenient to keep the correct results in an array of bit vectors, and
specify which column of the array a tree is supposed to be learning. This is
the purpose of the array correct_result and the integer bit_col.
The next parameter tset_size gives the number of elements in tset and
correct_result (which have to be the same --- there must be a result for
every input to the function).
The next two parameters control the amount of training that is to be done.
We train on the vectors of the training set in pseudo-random order. The
term epoch here is used to mean a number of input vector presentations equal
to the size of the training set. The parameter epochs states how many
epochs may be completed before training halts. The parameter no_correct
states how many elements in the training set the tree must get correct
during an epoch before training halts. The routine will therefore stop at
whichever of these two conditions is true first. For example given that we
have a training set with 10 elements and we wish to train for 15 epochs or
until 90% of the elements presented during an epoch have been responded to
correctly. We can achieve this by setting no_correct to 9 and epochs to 15.
The verbosity parameter controls how much diagnostic information the routine
will produce. At the moment only 0 (silent) or 1 (progress information) is
implemented. The progress information consists of popup message boxes which
require a user click on an "OK" button to continue (Future versions of the
software will have better progress information handling, which will not
require user supervision).
The routine decides which vector is the next to be presented to the tree and
extracts the result bit from the correct_result array. It also keeps track
of the number of epochs, and the number of correct responses from the tree.
The process of training is done by the private train() routine.
-11-
3.7.6 public void atree_print(tree,verbosity)
LPATREE tree;
int verbosity;
This routine allows the programmer to output an atree to disk before,
during, or after training, in a form suitable for printing. The parameter
tree is the tree to be printed, and verbosity is the amount of information
produced. The disk file is currently hard coded as "atree.out" (future
versions of the software will allow user selected output streams).
The routine makes an immediate call to the private print_tree routine.
3.7.7 public void atree_free(tree)
LAPTREE tree;
This routine frees up the atree pointed to by tree. It descends the
structure, searching for nodes that are the beginning of new segment blocks,
as indicated by tree->seg_flag.
3.7.8 public LPBIT_VEC bv_create(length)
int length;
Creates a vector of length bits, where each bit is initialised to 0, and
returns a long pointer to the bit vector.
3.7.9 public LPBIT_VEC bv_pack(unpacked,length)
LPSTR unpacked; (LPSTR is Windows for "char far *")
int length;
This routine has been provided to make it easy for the programmer to produce
bit vectors. The routine is handed an array of characters containing the
value 0 or 1 (unpacked) and an integer length giving the number of bits. The
routine returns a long pointer to a bit_vec.
3.7.10 public int bv_diff(v1,v2)
LPBIT_VEC v1;
LPBIT_VEC v2;
This routine calculates the Hamming distance between v1 and v2, i.e.
weight (v1 XOR v2)
where weight is the number of one bits in a vector and XOR is the bitwise
exclusive-or operation. This routine is used to find the closest vector in a
random walk array to some arbitrary vector. Just search through the random
walk for the vector with the smallest difference from the vector of tree
output bits. (Inefficient, but easier to understand than decoding an
algebraic code!).
-12-
3.7.11 public LPBIT_VEC bv_concat(n,vectors)
int n;
LPBIT_VEC far *vectors;
This routine is used by the programmer to join several bit vectors
end-to-end to give the string concatenation of the vectors. This routine is
most frequently used during the construction of training sets when elements
of several random walks have to be joined together to obtain an input vector
to a tree.
The parameter vectors is an array of bit_vec pointers, and the parameter n
states how many of them there are. Vector pointers are used to make this
routine a little faster since there is less copying involved. A long
pointer to the concatenated bit_vec is returned.
3.7.12 public void bv_print(stream, vector)
FILE *stream;
LPBIT_VEC vector;
This is a diagnostic routine used to print out a bit_vec.
3.7.13 public void bv_set(n,vec,bit)
int n;
LPBIT_VEC vec;
BOOL bit;
This routine allows the programmer to explicitly set (or reset) the nth bit
(0 to bit_vec.len - 1) bit in the vector vec to have the value in the
parameter `bit'.
3.7.14 public BOOL bv_extract(n,vec)
int n;
LPBIT_VEC vec;
This routine returns the value of the nth bit (0 to bit_vec.len - 1) in the
bit vector vec. The rather unpleasant expression works as follows :-
The parameter n is divided by eight to get the number of the byte where the
bit is held. This number is added to the first byte to get the actual
address of the byte concerned.
The remainder of the division n % BYTE is used to find where in the
byte, the bit is. A mask is shifted left this number of times and logically
and-ed with the byte. If the result is 0 the bit was 0. If the result
is greater than one, the bit was 1. The test for equality to zero forces the
result to be just 1 or 0.
-13-
3.7.15 public BOOL bv_equal(v1,v2)
LPBIT_VEC v1;
LPBIT_VEC v2;
This routine tests two bit vectors for equality.
3.7.16 public void bv_free(vector)
LPBIT_VEC vector;
This routine frees the memory used by a bit_vec, accessing a bit_vec after
it has been freed is usually disastrous.
3.7.17 public void Windows_Interrupt(cElapsed)
DWORD cElapsed; (DWORD is Windows for "unsigned long")
When called, this procedure allows Windows to multitask an atree application
with other Windows applications. This is accomplished with a PeekMessage()
call (see the Windows Programmer's Reference for more details). The
programmer may want to use this procedure during long tree evaluation and
training set generation loops, or during other processing where control may
not be passed back to the application's window procedure for lengthy periods
of time (the price you pay for non-preemptive multitasking!). Since
PeekMessage() calls can be quite time consuming, this procedure will only
call PeekMessage() after cElapsed milliseconds have passed since the last
call to PeekMessage(). Experimentation has shown a value for cElapsed of
about 1500 to work fairly well.
3.7.18 public LPSTR WinMem_Malloc(wFlags, wBytes)
WORD wFlags; (WORD is Windows for "unsigned int(16-bit)")
WORD wBytes;
Since the segmented memory architecture of DOS based PC's can cause great
grief when allocating large amounts of memory, the atree package includes
its own memory manager. Requests for memory are obtained from dynamically
allocated segments from the global heap in which local heaps have been
initialized. The memory is actually allocated by Windows' local heap
manager, and the resultant near (16 bit) pointer is combined with the global
segment descriptor to form a long (32 bit) pointer suitable for use in
Windows applications. wFlags indicate the kind of memory to allocate,
usually LMEM_MOVEABLE, and wBytes indicate the number of bytes to allocate.
See the Windows Programmer's Reference LocalAlloc() routine for more
information on the different values wFlags may take on. For ease of use,
the programmer may simply wish to use the Malloc(wBytes) macro, which
expands to WinMem_Malloc(LMEM_MOVEABLE, wBytes).
-14-
3.7.19 public LPSTR WinMem_Free(lpfree)
LPSTR lpfree;
This function frees the block of memory pointed to by lpfree, which is
decomposed into a segment selector, which is used to identify the global
segment from which the near pointer was allocated from, and a near pointer,
which is used by Windows' LocalFree() to free memory from the local heap in
the dynamically allocated segment. If there remains no more allocated
memory in the local heap(indicated by the freemem variable, the global
segment is deallocated. For ease of use, the Free(lp) macro expands to
WinMem_Free((LPSTR) lp).
The function returns NULL if successful, otherwise it returns lpfree.
3.8 Private atree Routines
The following routines are internal to the atree software, and cannot be
called by atree applications.
3.8.1 int LibMain(hInstance, wDataSeg, wHeapSize, lpzsCmdLine)
HANDLE hInstance;
WORD wDataSeg;
WORD wHeapSize;
LPSTR lpszCmdLine;
This routine serves as the entry point for the DLL version af the atree
software. It should be commented out if the programmer wishes to compile
and link atree.c directly with an atree application.
3.8.2 private void WinMem_Init()
This routine initializes the atree memory manager, and is called the first
time atree.dll is loaded.
3.8.3 private LPATREE build_tree(connection,....)
int *connection;
bool *complemented;
int start;
int end;
LPATREE tree;
This is the recursive routine that does most of the work when creating an
atree. It has an array of leaf-to-bit-vector connections (connection) and
another array telling it which of the connections are to be inverted
(complemented). It has a start and an end parameter which mark the part of
the connection array this subtree is connected to.
The routine allocates a single node, and then makes a decision based on the
size of the remaining subtree (which it knows from the start and end
parameters). The simplest case is when there is a difference of four or more
between start and end. Under these circumstances the routine recursively
-15-
calls itself to allocate the left and right subtrees. The left subtree is
allocated immediately after the current node, and the right subtree is
allocated after the left subtree. It is able to do this since build_tree()
always returns the next available space for node allocation.
If the difference between start and end is less than four, the routine
allocates some leaves using the information in the connection and
complemented arrays to specify how the input vector is to be accessed.
3.8.4 private void print_tree(tree,indent,verbosity,hOut)
LPATREE tree;
int indent;
int verbosity;
int hOut;
This routine does most of the work of printing out trees. It recursively
calls itself with a larger "indent" to print out the rightmost subtree, then
it prints out information about the current node, then recursively calls
itself again to print out the right subtree. This particular order was
chosen so that if the printout is tipped onto its side, it will resemble the
usual diagram of a tree.
The verbosity can currently be set to 0 (tree structure) or 1 (signal
values).
hOut is the internal file handle used to access atree.out.
3.8.5 private bool train(tree,vec,result)
LPATREE tree;
LPBIT_VEC vec;
bool result;
This routine trains a particular to return the given result
when it sees the given bit vector vec. It does this by working out the
current response of the tree to the vector using atree_eval() then
adapting the tree using the private adapt() routine.
3.8.6 private void adapt(tree,vec,result)
LPATREE tree;
LPBIT_VEC vec;
bool result;
This routine contains the heuristic responsibility algorithm. We define two
macros which are to be used locally, INCR and DECR, they are used to
increment and decrement the atree.cnt_10 and atree.cnt_01 counters which are
bounded by the constants MAXSET and MINSET.
The adaptation algorithm works its way recursively down the tree changing
the counters on nodes that are determined to be "heuristically responsible".
If a node is determined to be heuristically responsible, the algorithm
requires the evaluation of unevaluated subtrees to proceed --- this may not
-16-
have been completed by the evaluation stage of train() because of
parsimony(2). So the left and right subtrees are evaluated at this stage if
necessary.
The next stage is to update one of the counters; if the left subtree has the
value 1 and the right subtree has value 0, then the cnt_10 counter is the
one changed. If the desired result of the tree is 1, it is incremented,
otherwise it is decremented. The other counter cnt_01 is left unchanged,
since it only changes when the left subtree is 0 and the right subtree is 1.
The function value of the node may now have changed, so this is recomputed.
Finally, a fairly complex condition is used to decide whether either the
left or right subtree, or both, are heuristically responsible and thus
should be adapted in turn. The source code is the most concise definition of
this and it is recommended that you examine the code directly. The
heuristics used are intended to solve the "credit assignment problem", i.e.
they determine which nodes are responsible for the correct or incorrect
result of the tree. The success of these heuristics depends a lot on the
fact that the allowed node functions are monotonic. Finding good heuristics
for assigning responsibility is the most difficult question in connection
with using adaptive logic networks.
3.8.7 private char node_function(tree)
LPATREE tree;
This routine determines the action of a node (AND, OR, LEFT, RIGHT) from the
value of its counters.
3.8.8 error()
This is a last ditch routine called by atree_rand_walk() if it
can not proceed further.
_______
(2) laziness!
-17-
4 The Language lf
~ ~~~ ~~~~~~~~ ~~
The second major product included in the current release is the "lf"
language interpreter that allows a non-programmer to experiment with tree
adaptation. The user specifies a training set, and a test set, and selects
the encoding and quantization levels for a particular experiment. The
interpreter checks the statements for errors then executes the desired
experiment, finally outputting a table comparing the desired function with
the function actually learned. Various post-processors can use the
information to produce histograms of error or plots of the functions.
It is recommended that the user read and understand [Arms5] before using this
language.
There are two versions of lf: LF.EXE and LFEDIT.EXE. LF.EXE inputs a file
"lf.in" and outputs to a file "lf.out". LFEDIT.EXE is an interactive
editor, but can only handle files of about 48K. Use LF.EXE to test SPHERE.LF.
4.1 multiply.lf
The language is best learned by examining an example. The file multiply.lf
contains a simple experiment where we are trying to teach the system the
multiplication table. The program is divided into a "tree" section which
describes the tree and the length of training, and a "function" section
which describes the data to be learned. Comments are started with a `#' mark
and continue to the end of the line.
# A comment.
tree
size = 4000
min correct = 143
max epochs = 20
The tree and function sections can be in any order, in this particular
example the tree is described first. Apart from comments, tabs and newlines
are not significant; the arrangement chosen above is only for readability.
The first line after tree tells the system how large the atree is going to
be. In this case we are choosing a tree with 4000 leaves (3999 nodes). We
are going to train it until it gets 143 correct from the training set, or
for 20 complete presentations of the training set, whichever comes first.
The statements in the tree section may be in any order.
function
domain dimension = 2
coding = 32:12 32:12 32:7
quantization = 12 12 144
training set size = 144
training set =
1 1 1
1 2 2
1 3 3
1 4 4
....
-18-
test set size = 144
test set =
1 1 1
1 2 2
1 3 3
1 4 4
....
The training set MUST start with a dimension statement which gives the
number of columns in the function table. Currently the codomain size is
restricted to one so we are defining a problem with 3 columns --- 2 input
and one output.
The other statements may come in any order; note however that the definition
of the training set size must be defined before the training set. This also
applies to the test set definition.
The coding statement defines is a series of <width>:<step> definitions, one
for each column. The <width> is the number of bits in the bit vector for
that column, the <step> is the step size of the walk in Hamming space that
defines the encoding of this column. Because a tree only produces a single
bit in response to an input vector, the <width> of the codomain column (the
last one) actually defines how many trees will be learning output bits of
this function.
The quantization statement defines for each column, the total number of
coded bit vectors for that column. Entries in the test and training sets are
encoded into the nearest step, so this statement defines the accuracy
possible.
If a particular column is has a coding entry 1:1, it is treated as a special
case, a boolean column. Only values of 0, representing false, and 1,
representing true, make any sense in this column (although this is not
currently checked).
The training set statement defines the actual function to be learned by the
system. An entry in a table can be either a real number or an integer at the
moment. Boolean values are special cases of integers.
The test set statement defines the test that is run on the trees at the end
of training to see how well the learned function performs. Like the test
set, reals or integers are acceptable.
After lf has executed, it produces a table of output showing how each
element in the test set was quantized, and the value the trained tree
returned. Consider the following results that multiply.lf produced.
.....
3.000000 2 11.000000 10 33.000000 32 32.777779 32
3.000000 2 12.000000 11 36.000000 35 35.756945 35
4.000000 3 1.000000 0 4.000000 3 3.979167 3
4.000000 3 2.000000 1 8.000000 7 7.951389 7
4.000000 3 3.000000 2 12.000000 11 11.923611 11
.....
Each column consists of two numbers, the entry specified by the user, and
an integer describing the quantization level it was coded into.
-19-
The fourth column is the result produced by the trained tree. It shows the
quantization level produced (the second figure) and how this may be
interpreted in the space of the codomain (the first figure).
4.2 sphere.lf
This lf example uses a spherical harmonic function Y2 defined by:
Y2(µ, φ) = A0(3µ²/2 - 1/2)
+ 3µ(1 - µ²)^½ [A1 cos φ + B1 sin φ]
+ 3(1 - µ²) [A2 cos 2φ + B2 sin 2φ]
where A0 = 1.0, A1 = 0.4, B1 = 0.9, A2 = 2.4, B2 = 7.9. The values of µ
were in the interval [0.0, 1.0], and the values of φ were in [0.0, π]. The
values of Y2 range between -26.0 and 26.0.
The µ and φ intervals were quantized into 100 levels each; the random walks
had 64 bits and a stepsize of 3. The Y2 values were quantized into 100
levels, the random walk having 64 bits with a stepsize of 3. Training 64
networks of 8191 elements on 1000 samples resulted in a function which,
during test on 1000 new samples, was decoded to the correct quantization
level, plus or minus three, 88.6\% of the time. The error in the quantized
result was no more than nine quantization levels for all of the test
samples. (A slightly better learning algorithm got within three levels
95.8\% of the time, and was always within eight levels.)
The function section introduces the optional "largest" and "smallest"
statements. These may be used if the user needs to explicitly define the
largest and smallest values in the test and training sets. If they are
missing, lf will just use the largest and smallest values for each column in
both the test and training sets.
This problem takes about 80 minutes of CPU time on a Sun Sparcstation 1. We
have included a sample set of results in the file sphere.out.
4.3 The Syntax of lf
~~~ ~~~ ~~~~~~ ~~ ~~
The syntax has been defined using YACC. Tokens have been written in quotes
to distinguish them. Note that the following tokens are synonyms :-
dimension, dimensions
max, maximum
min, minimum
The syntax is defined as follows :-
program : function_spec tree_spec
| tree_spec function_spec
function_spec : "function" dimension function_statements
dimension : "domain dimension =" integer
function_statements : function_statement
| function_statements function_statement
-20-
function_statement : quantization
| coding
| train_table_size
| train_table
| test_table_size
| test_table
| largest
| smallest
quantization : "quantization =" quant_list
quant_list : integer
| quant_list integer
coding : "coding =" code_list
code_list : integer ":" integer
| code_list integer ":" integer
train_table_size : "training set size =" integer
train_table : "training set =" table
test_table_size : "test set size =" integer
test_table : "test set =" table
table : num
| table num
num : real
| integer
largest : "largest =" largest_list
largest_list : num
| largest_list num
smallest : "smallest =" smallest_list
smallest_list : num
| smallest_list num
tree_spec : "tree" tree_statements
tree_statements : tree_statement
| tree_statements tree_statement
tree_statement : tree_size
| max_correct
| max_epochs
tree_size : "size =" integer
max_correct : "min correct =" integer
max_epochs : "max epochs =" integer
-21-
5 Other Demonstrations
~ ~~~~~ ~~~~~~~~~~~~~~
In this section we briefly present some boolean function problems
which atrees have solved.
5.1 The Multiplexor Problem
A multiplexor is a digital logic circuit which behaves as follows: there are
k input leads called control leads, and 2^k leads called the "other" input
leads. If the input signals on the k control leads represent the number j
in binary arithmetic, then the output of the circuit is defined to be equal
to the value of the input signal on the jth one of the other leads (in some
fixed order). A multiplexor is thus a boolean function of n = k + 2^k
variables and is often referred to as an n-multiplexor.
Here is a program to define a multiplexor with three control leads, v[2],
v[1] and v[0], the fact that they are these particular variables being
irrelevant due to randomization in the programs:
/* Windows window procedure and initialization omitted for clarity */
/* An eleven input multiplexor function test */
#include <stdio.h>
#include <stdlib.h>
#include <windows.h>
#include "atree.h"
#define TRAINSETSIZE 2000
#define WIDTH 11
#define TESTSETSIZE 1000
#define TREESIZE 2047
char multiplexor(v)
char *v;
{
return(v[ v[2]*4 + v[1]*2 + v[0] + 3]);
}
main()
{
int i;
int j;
LPBIT_VEC training_set;
LPBIT_VEC icres;
LPBIT_VEC test;
char vec[WIDTH];
char ui[1];
int correct = 0;
LPATREE tree;
char szBuffer[80];
-22-
/* Initialise */
training_set = (LPBIT_VEC) Malloc (TRAINSETSIZE * sizeof(bit_vec));
MEMCHECK(training_set);
icres = (LPBIT_VEC) Malloc (TRAINSETSIZE * sizeof(bit_vec));
MEMCHECK(icres);
atree_init();
/* Create the test data */
MessageBox(NULL, "Creating training data", "Multiplexor", MB_OK);
for (i = 0; i < TRAINSETSIZE; i++)
{
for (j = 0; j < WIDTH; j++)
{
vec[j] = RANDOM(2);
}
training_set[i] = *(bv_pack(vec,WIDTH));
ui[0] = multiplexor(vec);
icres[i] = *(bv_pack(ui,1));
}
/* Create a tree and train it */
MessageBox(NULL,"Training tree", "Multiplexor", MB_OK);
tree = atree_create(WIDTH,TREESIZE);
(void) atree_train(tree,training_set,icres,0,TRAINSETSIZE,
TRAINSETSIZE-1,100,1);
/* Test the trained tree */
MessageBox(NULL,"Testing the tree", "Multiplexor", MB_OK);
for (i = 0; i < TESTSETSIZE; i++)
{
for (j = 0; j < WIDTH; j++)
{
vec[j] = RANDOM(2);
}
test = bv_pack(vec,WIDTH);
if (atree_eval(tree,test) == multiplexor(vec))
{
correct++;
}
bv_free(test);
}
wsprintf(szBuff,"%d correct out of %d in final test",correct,TESTSETSIZE);
/* discard training set */
for (i = 0; i < TESTSETSIZE; i++)
{
Free(training_set[i].bv);
Free(icres[i].bv);
}
-23-
Free(training_set);
Free(icres);
/* Discard tree */
atree_free(tree);
return;
}
This problem was solved to produce a circuit testing correctly on 99.4\% of
1000 test vectors in 19 epochs, or about 530 seconds on a Sun 3/50. The
time may vary considerably depending on the random numbers used. It is
possible to learn multiplexors with twenty inputs (four control leads) with
a straightforward but improved adaptation procedure, and multiplexors with
up to 521 leads (nine of them control leads) using much more elaborate
procedures which change the tree structure during learning [Arms5].
5.2 The Mosquito Problem
Suppose we are conducting medical research on malaria, and we don't know yet
that malaria is caused by the bite of an anopheles mosquito, unless the
person is taking quinine (in Gin and Tonics, say) or has sickle-cell
anaemia. We are inquiring into eighty boolean-valued factors of which
"bitten by anopheles mosquito", "drinks Gin and Tonics", and "has
sickle-cell anaemia" are just three. For each of 500 persons in the sample,
we also determine whether or not the person has malaria, represented by
another boolean value, and we train a network on that data. We then test
the learned function to see if it can predict, for a separately-chosen test
set, whether person whose data were not used in training has malaria.
Suppose on the test set, the result is 100% correct. (Training and test can
be done in about five seconds on a Sun Sparcstation 1.) Then it would be
reasonable to analyse the function produced by the tree, and note all the
variables among the eighty that are not involved in producing the result. A
complete data analysis system would have means of eliminating subtrees "cut
off" by LEFT or RIGHT functions, to produce a simple function which would
help the researcher understand some factors important for the presence of
the disease. If there were extraneous variables still left in the function
in one trial, perhaps they would not show up in a second trial, so that one
could see what variables are consistently important in drawing conclusions
about malaria.
We apologize for the simplistic example, however we feel the technique of
data analysis using these trees may be successful in cases where there are
complex interactions among features which tend to mask the true aetiology of
the disease.
The code for the problem can be found in mosquito.c.
-24-
6 References
~ ~~~~~~~~~~
[Arms] W. W. Armstrong, J. Gecsei: Adaptation Algorithms for
Binary Tree Networks, IEEE Trans. on Systems, Man and Cybernetics,
SMC-9 (1979), pp. 276 - 285.
[Arms2] W. W. Armstrong, Adaptive Boolean Logic Element, U. S.
Patent 3,934,231, Jan. 20, 1976, assigned to Dendronic Decisions
Limited.
[Arms3] W. W. Armstrong, J. Gecsei, Architecture of a Tree-Based
Image Processor, 12th Asilomar Conf. on Circuits, Systems and
Computers, IEEE Cat. No. 78CHI369-8 C/CAS/CS Nov. 1978, 345-349.
[Arms4] W. W. Armstrong, G. Godbout, Properties of binary trees
of flexible elements useful in pattern recognition, Proc. IEEE Int'l.
Conf. on Cybernetics and Society, San Francisco (1975) 447 - 450.
[Arms5] W. W. Armstrong, Jiandong Liang, Dekang Lin, Scott Reynolds,
Experiments using Parsimonious Adaptive Logic, Technical Report
TR 90-30, Department of Computing Science, University of Alberta,
September 1990.
[Boch] G. v. Bochmann, W. W. Armstrong: Properties of Boolean
Functions with a Tree Decomposition, BIT 14 (1974), pp. 1 - 13.
[Hech] Robert Hecht-Nielsen, Neurocomputing, Addison-Wesley,
1990.
[Meis] William S. Meisel, Parsimony in Neural Networks, Proc.
IJCNN-90-WASH-DC, vol. I, pp. 443 - 446.
[Rume] D. E. Rumelhart and J. L. McClelland: Parallel
Distributed Processing, vols. 1&2, MIT Press, Cambridge, Mass. (1986).
[Smit] Derek Smith, Paul Stanford: A Random Walk in Hamming
Space, Proc. Int. Joint Conf. on Neural Networks, San Diego, vol. 2
(1990) 465 - 470.
7 Acknowledgements
~ ~~~~~~~~~~~~~~~~
I'd like to thank Bill Armstrong for going through this document and
correcting it. His mark can be seen on some of my footnotes. Alas, there are
bound to be various errors and omissions still present, and for these, I
apologize in advance.
A. Dwelly
I'd like to thank Andy Dwelly for being patient with me while learning the
atree code, and for realizing that ports of 32 bit UNIX software
to a 16 bit segmented memory O/S merit having separate source files (death
to #ifdef WINDOWS). Also, I apologize for any errors I have inadvertently
propagated or created!
M. Thomas
-25-
